{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K-th Symbol in Grammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthGrammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第K个语法符号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们构建了一个包含 <code>n</code> 行(&nbsp;<strong>索引从 1&nbsp; 开始&nbsp;</strong>)的表。首先在第一行我们写上一个 <code>0</code>。接下来的每一行，将前一行中的<code>0</code>替换为<code>01</code>，<code>1</code>替换为<code>10</code>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，对于 <code>n = 3</code> ，第 <code>1</code> 行是 <code>0</code> ，第 <code>2</code> 行是 <code>01</code> ，第3行是 <code>0110</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定行数&nbsp;<code>n</code>&nbsp;和序数 <code>k</code>，返回第 <code>n</code> 行中第 <code>k</code>&nbsp;个字符。（&nbsp;<code>k</code>&nbsp;<strong>从索引 1 开始</strong>）</p>\n",
    "\n",
    "<p><br />\n",
    "<strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1, k = 1\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释: </strong>第一行：<u>0</u>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2, k = 1\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> \n",
    "第一行: 0 \n",
    "第二行: <u>0</u>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2, k = 2\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong>\n",
    "第一行: 0\n",
    "第二行: 0<u>1</u>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 2<sup>n - 1</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-th-symbol-in-grammar](https://leetcode.cn/problems/k-th-symbol-in-grammar/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-th-symbol-in-grammar](https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1', '2\\n1', '2\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        return (k-1).bit_count() & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        if 1 == 0:  # Recursion\n",
    "            # 0\n",
    "            # 0 1\n",
    "            # 0 1 1 0\n",
    "            # 0 1 1 0 1 0 0 1\n",
    "            # 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0\n",
    "            if k == 1:\n",
    "                return retVal\n",
    "            if k > (1 << (n - 2)):\n",
    "                retVal = 1 ^ self.kthGrammar(n - 1, k - (1 << (n - 2)))\n",
    "                return retVal\n",
    "            retVal = self.kthGrammar(n - 1, k)\n",
    "        else:   # Bit Manipulation: 0->01, 1-> 10.\n",
    "            # +-------------------------------+\n",
    "            # | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |\n",
    "            # +-------------------------------+\n",
    "            # | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |\n",
    "            # +-------------------------------+\n",
    "            # | 0 | 1 |   |   |   |   |   |   |\n",
    "            # |   | 1 | 1 | 0 |   |   |   |   |\n",
    "            # |   |   | 1 |   | 1 | 0 |   |   |\n",
    "            # |   |   |   | 0 |   |   | 0 | 1 |\n",
    "            # +-------------------------------+\n",
    "            # retVal = (k - 1).bit_count() & 1\n",
    "            k -= 1\n",
    "            while k:\n",
    "                k &= (k - 1)\n",
    "                retVal ^= 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        cnt=0\n",
    "        k-=1\n",
    "        while k>0:\n",
    "            cnt+=k&1\n",
    "            k>>=1\n",
    "        return cnt&1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        return(k-1).bit_count() & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        # 判断k是否大于当前n行长度的一半\n",
    "        l = 2**(n-1)\n",
    "        # k在后半段，k的值为n行第(k-l//2)个值取反\n",
    "        if k > (l >> 1):\n",
    "            return 1 - self.kthGrammar(n-1, k - (l>>1))\n",
    "        # k在前半段，只要返回n-1行第k个数字即可\n",
    "        else:\n",
    "            return self.kthGrammar(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return (k & 1) ^ 1 ^ self.kthGrammar(n - 1, (k + 1) // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "\n",
    "\n",
    "        if n==1: return 0\n",
    "        if n==2:\n",
    "            return [0,1][k-1]\n",
    "\n",
    "        def get_num(n,k):\n",
    "            if n==2:\n",
    "                return [0,1][k-1]\n",
    "            \n",
    "            if get_num(n-1,math.ceil(k/2))==0:\n",
    "                return 1 if k%2==0 else 0\n",
    "            else:\n",
    "                return 0 if k % 2 == 0 else 1\n",
    "\n",
    "        return get_num(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return (k & 1) ^ 1 ^ self.kthGrammar(n - 1, (k + 1) // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        return bin(k - 1).count('1') & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dic={1:[1,0],0:[0,1]}\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        return (k&1)^1^self.kthGrammar(n-1,(k+1)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        bk=[0 for i in range(n)]\n",
    "        t=k-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            bk[i]=t%2\n",
    "            t=t//2\n",
    "        cur=0\n",
    "        for i in bk:\n",
    "            if i==0 and cur==0:\n",
    "                cur=0\n",
    "            elif i==0 and cur==1:\n",
    "                cur=1\n",
    "            elif i==1 and cur==0:\n",
    "                cur=1\n",
    "            elif i==1 and cur==1:\n",
    "                cur=0\n",
    "        return cur\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        while k<=2**(n-1):\n",
    "            n-=1\n",
    "        return (self.kthGrammar(n-1,k-2**(n-1))+1)%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # return (k - 1).bit_count() & 1\n",
    "        k -= 1\n",
    "        res = 0\n",
    "        while k:\n",
    "            k &= k - 1\n",
    "            res ^= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # lastrow='0'\n",
    "        # i =1  \n",
    "        # while i<n:\n",
    "        #     lastrow = ''.join('01' if x=='0' else '10' for x in lastrow)\n",
    "        #     i+=1 \n",
    "        # return int(lastrow[k-1])\n",
    "\n",
    "        if n==1: return 0 \n",
    "        return (1-k%2) ^ self.kthGrammar(n-1,(k+1)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return (k & 1) ^ 1 ^ self.kthGrammar(n - 1, (k + 1) // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 可以发现：第 \n",
    "#  k个数字是由上一位对应位置上的数字生成的。\n",
    "\n",
    "#  k在奇数位时，由上一行 \n",
    "#  (k+1)/2位置的值生成。且与上一行 \n",
    "#  位置的值相同；\n",
    "#  在偶数位时，由上一行 \n",
    "#  位置的值生成。且与上一行 \n",
    "#  位置的值相反。\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if k % 2 == 1:\n",
    "            return self.kthGrammar(n - 1, (k + 1) // 2)\n",
    "        else:\n",
    "            return abs(self.kthGrammar(n - 1, k // 2) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # return (k - 1).bit_count() & 1\n",
    "        k -= 1\n",
    "        res = 0\n",
    "        while k:\n",
    "            k &= k - 1\n",
    "            res ^= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(self,n,k):\n",
    "        \n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        return self.kthGrammar(n-1,k)  if k<=2**(n-1) else (self.kthGrammar(n-1,k-2**(n-1))+1)%2\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        '''0\n",
    "        0 1\n",
    "        01 10\n",
    "        0110 1001\n",
    "        01101001 10010110'''\n",
    "        return self.func(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        if k > 2 ** (n-2):\n",
    "            return 1 - self.kthGrammar(n-1, k-2 ** (n-2) )\n",
    "        else:\n",
    "            return self.kthGrammar(n-1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "\n",
    "        def dfs(m, p):\n",
    "            if m == 1:\n",
    "                return \"0\"\n",
    "            i = (p - 1) % 2\n",
    "            x = dfs(m - 1, (p + 1) // 2)\n",
    "            return ind[x][i]\n",
    "        \n",
    "        ind = {\"0\": \"01\", \"1\": \"10\"}\n",
    "        return int(dfs(n, k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        def dfs(r, c, cur):\n",
    "            if r == 1:\n",
    "                return cur\n",
    "            if (c % 2 == 0 and cur == 0) or (c % 2 == 1 and cur == 1):\n",
    "                return dfs(r-1, (c-1)//2+1, 1)\n",
    "            else:\n",
    "                return dfs(r-1, (c-1)//2+1, 0)\n",
    "        return 1 if dfs(n, k, 1) == 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return (k & 1) ^ 1 ^ self.kthGrammar(n - 1, (k + 1) // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if k % 2 == 1:\n",
    "            return self.kthGrammar(n - 1, (k + 1) // 2)\n",
    "        else:\n",
    "            return abs(self.kthGrammar(n - 1, k // 2) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # return (k - 1).bit_count() & 1\n",
    "        k -= 1\n",
    "        res = 0\n",
    "        while k:\n",
    "            k &= k - 1\n",
    "            res ^= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "01\n",
    "0110\n",
    "01101001\n",
    "'''\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        def f(n,i):\n",
    "            if n==2:\n",
    "                if i==0:\n",
    "                    return 0\n",
    "                if i==1:\n",
    "                    return 1\n",
    "            ans=0\n",
    "            prev=f(n-1,i//2)\n",
    "            if prev==1 and i%2==0:\n",
    "                ans=1\n",
    "            if prev==0 and i%2==1:\n",
    "                ans=1\n",
    "            return ans\n",
    "        return f(n,k-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        while k<=2**(n-1):\n",
    "            n-=1\n",
    "        cnt=0\n",
    "        while k>2 and  k>2**(n-1):\n",
    "            k-=2**(n-1)\n",
    "            n-=1\n",
    "            cnt^=1\n",
    "        return (self.kthGrammar(n,k)+1)%2 if cnt==1 else self.kthGrammar(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if k <= (1 << (n - 2)):\n",
    "            return self.kthGrammar(n - 1, k)\n",
    "        return self.kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        l = 2**(n-1)\n",
    "        rev = 0\n",
    "        while n>1:\n",
    "            if k>l//2:\n",
    "                k -= l//2\n",
    "                rev = (rev+1)%2\n",
    "            else:\n",
    "                n-=1\n",
    "                l//=2\n",
    "        return rev "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        while k<=2**(n-1):\n",
    "            n-=1\n",
    "        cnt=0\n",
    "        while k>2 and  k>2**(n-1):\n",
    "            k-=2**(n-1)\n",
    "            n-=1\n",
    "            cnt^=1\n",
    "        return (self.kthGrammar(n,k)+1)%2 if cnt==1 else self.kthGrammar(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        while k<=2**(n-1):\n",
    "            n-=1\n",
    "        cnt=0\n",
    "        while k>2 and  k>2**(n-1):\n",
    "            k-=2**(n-1)\n",
    "            n-=1\n",
    "            cnt^=1\n",
    "        return (self.kthGrammar(n,k)+1)%2 if cnt==1 else self.kthGrammar(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        '''0\n",
    "        0 1\n",
    "        01 10\n",
    "        0110 1001\n",
    "        01101001 10010110'''\n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        return self.kthGrammar(n-1,k)  if k<=2**(n-1) else (self.kthGrammar(n-1,k-2**(n-1))+1)%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        if k%2:\n",
    "            return self.kthGrammar(n-1, (k+1)//2)\n",
    "        else:\n",
    "            return abs(self.kthGrammar(n-1, k/2)-1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        flag = 1\n",
    "        while n > 1:\n",
    "            if k > 2 ** (n - 2):\n",
    "                k -= 2 ** (n - 2)\n",
    "                n -= 1\n",
    "                flag *= -1\n",
    "            else:\n",
    "                n -= 1\n",
    "        return 0 if flag == 1 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        def search(k, n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if search((k + 1) // 2, n-1) == 0:\n",
    "                if k % 2 == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if k % 2 == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "        return search(k, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        v = self.kthGrammar(n-1, (k+1) // 2)\n",
    "        if k % 2 == 1:\n",
    "            # left\n",
    "            return v\n",
    "        else:\n",
    "            # right\n",
    "            return 1 - v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "key={\r\n",
    "    0:[0,1],\r\n",
    "    1:[1,0],\r\n",
    "}\r\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int,now=0) -> int:\r\n",
    "        if n==1:\r\n",
    "            return now\r\n",
    "        tmp=2**(n-2)\r\n",
    "        if k>tmp:\r\n",
    "            k-=tmp\r\n",
    "            return self.kthGrammar(n-1,k,key[now][1])\r\n",
    "        else:\r\n",
    "            return self.kthGrammar(n-1,k,key[now][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        一行第i个字符会在下一行的第2i和2i+1产生两个字符\n",
    "        如果第i个字符是0 那么两个分别是0 1 如果是1 那么是1 0\n",
    "        第2i个总是和第i个相同 2i+1则相反\n",
    "        因此看k是否为奇数 是就反转一次 然后k除以2 然后判断直到k为0 最后反转次数是否为奇数\n",
    "        上面的过程就等价于k的二进制有多少个1\n",
    "        \"\"\"\n",
    "        return (k - 1).bit_count() & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        v = self.kthGrammar(n-1, (k+1) // 2)\n",
    "        if k % 2 == 1:\n",
    "            # left\n",
    "            return v\n",
    "        else:\n",
    "            # right\n",
    "            return (v+1)%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "key={\r\n",
    "    0:[0,1],\r\n",
    "    1:[1,0],\r\n",
    "}\r\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int,now=0) -> int:\r\n",
    "        if n==1:\r\n",
    "            return now\r\n",
    "        tmp=2**(n-2)\r\n",
    "        if k>tmp:\r\n",
    "            k-=tmp\r\n",
    "            return self.kthGrammar(n-1,k,now^1)\r\n",
    "        else:\r\n",
    "            return self.kthGrammar(n-1,k,now)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        def grammar(n, k):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if k <= 2**(n-2):\n",
    "                return grammar(n-1, k)\n",
    "            else:\n",
    "                return 1 - grammar(n-1, k - 2**(n-2) )\n",
    "        return grammar(n, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if k <= (1 << (n-2)):\n",
    "            return self.kthGrammar(n-1, k)\n",
    "        return self.kthGrammar(n-1, k - (1 << (n-2))) ^ 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        flag = False\n",
    "        k = k-1\n",
    "        while n>=2:\n",
    "            if k>= (2**(n-2)):\n",
    "                flag = not flag\n",
    "                k = k-(2**(n-2))\n",
    "            n-=1\n",
    "        return int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        if k > 2 ** (n - 2):\n",
    "            return 1 ^ self.kthGrammar(n - 1, k - 2 ** (n - 2))\n",
    "        return self.kthGrammar(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # return (k - 1).bit_count() & 1\n",
    "        k -= 1\n",
    "        res = 0\n",
    "        while k:\n",
    "            k &= k - 1\n",
    "            res ^= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        return (len(str(bin(k)))+str(bin(k)).rstrip('0').count('0'))%2 if 2**n>=k else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        def grammar(n, k):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if k <= 2**(n-2):\n",
    "                return grammar(n-1, k)\n",
    "            else:\n",
    "                return 1 - grammar(n-1, k - 2**(n-2) )\n",
    "        return grammar(n, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if k % 2 == 0:\n",
    "            # even\n",
    "            if self.kthGrammar(n-1, k // 2) == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        else:\n",
    "            # odd\n",
    "            if self.kthGrammar(n-1, (k + 1) // 2) == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "key={\r\n",
    "    0:[0,1],\r\n",
    "    1:[1,0],\r\n",
    "}\r\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\r\n",
    "        res=0\r\n",
    "        for i in range(n-2,-1,-1):\r\n",
    "            tmp=2**i\r\n",
    "            if k>tmp:\r\n",
    "                k-=tmp\r\n",
    "                res=key[res][1]\r\n",
    "            else:\r\n",
    "                res=key[res][0]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\r\n",
    "        if n==1:\r\n",
    "            return 0\r\n",
    "        tmp=2**(n-2)\r\n",
    "        if k>tmp:\r\n",
    "            k-=tmp\r\n",
    "            return self.kthGrammar(n-1,k)^1\r\n",
    "        else:\r\n",
    "            return self.kthGrammar(n-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        n = 0\n",
    "        while k > 2:\n",
    "            for i in range(1, 2 ** 31):\n",
    "                if 2 ** i >= k:\n",
    "                    k -=  2 ** (i - 1)\n",
    "                    n += 1\n",
    "                    break\n",
    "        #print(k)\n",
    "        if n % 2 == 0:\n",
    "            return int('01'[k - 1])\n",
    "        else:\n",
    "            return int('10'[k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        '''0\n",
    "        0 1\n",
    "        01 10\n",
    "        0110 1001\n",
    "        01101001 10010110'''\n",
    "        # l=1\n",
    "        # nums=[0]\n",
    "        # def trans(nums):\n",
    "        #     for i,num in enumerate(nums):\n",
    "        #         nums[i]=num^1\n",
    "        #     return nums[:]\n",
    "        # while l<k:\n",
    "        #     nums=nums+trans(nums[:])\n",
    "        #     l*=2\n",
    "        # # print(nums)\n",
    "        # return nums[k-1]\n",
    "        # if n==1:\n",
    "        #     return 0 \n",
    "        # elif n==2:\n",
    "        #     return k-1\n",
    "        if k<=2:\n",
    "            return k-1\n",
    "        return self.kthGrammar(n-1,k)  if k<=2**(n-1) else 1^self.kthGrammar(n-1,k-2**(n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if k%2:\n",
    "            return self.kthGrammar(n-1,(k+1)/2)\n",
    "        else:\n",
    "            return abs(self.kthGrammar(n-1,k/2)-1)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # [2*n-1,2*n]\n",
    "    def get(self,n,k):\n",
    "        if n==1:return 0\n",
    "        t=self.get(n-1,(k+1)//2)\n",
    "        if t==0:\n",
    "           return 1 if k%2==0 else 0 \n",
    "        if t==1:\n",
    "           return 0 if k%2==0 else 1\n",
    "\n",
    "        \n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        return self.get(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        last_index = (k+1)//2\n",
    "        position = (k+1)%2\n",
    "        last = self.kthGrammar(n-1,last_index)\n",
    "        if last:\n",
    "            if position:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        else:\n",
    "            if position:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        # 判断k是否大于当前n行长度的一半\n",
    "        l = 2**(n-1)\n",
    "        # k在后半段，k的值为n行第(k-l//2)个值取反\n",
    "        if k > (l >> 1):\n",
    "            return 1 ^ self.kthGrammar(n-1, k - (l>>1))\n",
    "        # k在前半段，只要返回n-1行第k个数字即可\n",
    "        else:\n",
    "            return self.kthGrammar(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        def dfs(n, k):\n",
    "            if n==1:return 0\n",
    "            father = dfs(n-1, k+1>>1)\n",
    "            return father if (k&1)==1 else 1^father\n",
    "        return dfs(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "key=[\r\n",
    "    [0,1],\r\n",
    "    [1,0],]\r\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\r\n",
    "        res=0\r\n",
    "        for i in range(n-2,-1,-1):\r\n",
    "            tmp=2**i\r\n",
    "            if k>tmp:\r\n",
    "                k-=tmp\r\n",
    "                res=key[res][1]\r\n",
    "            else:\r\n",
    "                res=key[res][0]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(n, k):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            half = 2**(n-1) // 2\n",
    "            if k <= half:\n",
    "                return func(n-1, k)\n",
    "            else:\n",
    "                return 1 - func(n-1, k - half)\n",
    "        \n",
    "        return func(n, k)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return (k & 1) ^ 1 ^ self.kthGrammar(n - 1, (k + 1) // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "key={\r\n",
    "    0:[0,1],\r\n",
    "    1:[1,0],\r\n",
    "}\r\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\r\n",
    "        res=0\r\n",
    "        for i in range(n-2,-1,-1):\r\n",
    "            if k>2**i:\r\n",
    "                k-=2**i\r\n",
    "                res=key[res][1]\r\n",
    "            else:\r\n",
    "                res=key[res][0]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        return (k - 1).bit_count() & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        n -= 1\n",
    "        k -= 1\n",
    "        v = 0\n",
    "        while(n >= 0):\n",
    "            if(k % 2 == 0):\n",
    "                if(v == 0):\n",
    "                    v = 0\n",
    "                else:\n",
    "                    v = 1\n",
    "            else:\n",
    "                if(v == 0):\n",
    "                    v = 1\n",
    "                else:\n",
    "                    v = 0\n",
    "            k = k // 2\n",
    "            n -= 1\n",
    "        return 0 if v == 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # 0 01 0110 01101001 \n",
    "        if n==1:\n",
    "            return 0\n",
    "        if k<=(1<<(n-2)):\n",
    "            return self.kthGrammar(n-1,k)\n",
    "        else:\n",
    "            return self.kthGrammar(n-1,k-(1<<(n-2))) ^ 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        father = self.kthGrammar(n - 1, (k + 1) // 2)\n",
    "        return father if k & 1 else father ^ 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, N, K):\n",
    "        if N == 1:\n",
    "            return 0\n",
    "        if K <= 2 ** (N - 2):\n",
    "            return self.kthGrammar(N - 1, K)\n",
    "        else:\n",
    "            return 1 - self.kthGrammar(N - 1, K - 2 ** (N - 2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if k <= (1 << (n - 2)):\n",
    "            return self.kthGrammar(n - 1, k)\n",
    "        return 1 - self.kthGrammar(n - 1, k - (1 << (n - 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        overturn_cnt = 0  # 翻转次数\n",
    "        for i in range(n):\n",
    "            if k%2 == 0:\n",
    "                if k == 2:\n",
    "                    if overturn_cnt%2 == 0:\n",
    "                        return 1\n",
    "                    else:\n",
    "                        return 0\n",
    "                else:\n",
    "                    k /= 2\n",
    "                    overturn_cnt += 1\n",
    "            else:\n",
    "                if k == 1:\n",
    "                    if overturn_cnt%2 == 0:\n",
    "                        return 0\n",
    "                    else:\n",
    "                        return 1\n",
    "                else:\n",
    "                    k = (k-1)/2+1\n",
    "# 0\n",
    "# 0 1\n",
    "# 0 1 1 0\n",
    "# 0 1 1 0 1 0 0 1\n",
    "# 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        # 0 01 0110 01101001 \n",
    "        if n==1:\n",
    "            return 0\n",
    "        if k<=(2**(n-2)):\n",
    "            return self.kthGrammar(n-1,k)\n",
    "        else:\n",
    "            return 1-self.kthGrammar(n-1,k-2**(n-2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return (k&1) ^ 1 ^ self.kthGrammar(n - 1, (k + 1) // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        reverse=0\n",
    "        while n > 1 :\n",
    "            h_leaf=2**(n-1)/2\n",
    "            if k > h_leaf:\n",
    "                reverse+=1\n",
    "                k-=h_leaf\n",
    "            n-=1\n",
    "        if reverse % 2 == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        recursion\r\n",
    "        - 若是parent的left child, 则和parent相同，否则相反\r\n",
    "        - 透過k是奇數還是偶數來判斷是parent的left child還是right child\r\n",
    "    \"\"\"\r\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\r\n",
    "        if n == 1: return 0 # base case\r\n",
    "        res = self.kthGrammar(n-1, (k+1)//2) # parent\r\n",
    "        return res ^ 1 if k % 2 == 0 else res # left child or right child"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def kthGrammar(self, n: int, k: int) -> int:\r\n",
    "\r\n",
    "        # 递归法 对第n行第k个元素的生成过程进行溯源\r\n",
    "        # based on the rule of 0->01 and 1->10,\r\n",
    "        # when the remainder of k % 2 equals to 0, the element unchanges,\r\n",
    "        # while the remainder of k % 2 equals to 1, the element needs to be negated (取反)\r\n",
    "        def tracert(n, k):\r\n",
    "            if n == 1:\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return tracert(n-1, k // 2) if k % 2 == 0 else ~tracert(n-1, k // 2)\r\n",
    "            \r\n",
    "        return 1 if tracert(n, k-1) else 0\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
